Ray tracing is a technique that involves finding intersections of given rays with geometric objects in a scene. Ray tracing can be used to create a more pleasing and rich 3D experience compared with traditional rasterization approaches, as it approximates natural light propagation more accurately.
Because ray tracing may involve many ray-polygon intersection tests, some additional structures, known as “acceleration structures”, may be used to minimize the number of ray/polygon intersection tests. Acceleration structures may include linked data arrays containing information about the geometric detail in a 3D scene (e.g., bounding box coordinates), which enables a ray trajectory to be traced through a scene in a more logarithmic amount of time compared to the amount of time necessary to test every ray against every polygon within a scene or object in a scene. There are many types of acceleration structures, including “kd-tree” acceleration structures, which contain “nodes” representing 3D space divided into two sub-spaces by a split plane. In a kd-tree, the leaf nodes of the tree contain polygons intersecting the bounding box of the leaf node. Typically, in an acceleration structure, such as a kd-tree, larger bounding boxes are represented at the highest level of the hierarchy and progressively smaller bounding boxes are at the bottom of the structure.
Creating acceleration structures, such as kd-trees, can be computationally expensive. Smaller acceleration structures are faster to create, but they eliminate fewer ray-polygon intersection tests. The optimal size of the acceleration structure is dependent on how fast it could be traversed compared with the average speed of the used ray-triangle intersection test.